from collections import defaultdict
for ik in range(int(input())):
s=list(input())
n=len(s)
w,m=map(int,input().split())
arr=[0]
for q in range(n):
arr.append(arr[-1]*10+int(s[q]))
arr[-1]%=9
def calc(x,y):
num=arr[y]-arr[x-1]*pow(10,x,9)
return num%9
ind=defaultdict(list)
for i in range(1,n-w+2):
ind[calc(i,i+w-1)].append(i)
for i in range(m):
ans = (10 ** 9, 10 ** 9)
l,r,k=map(int,input().split())
q=calc(l,r)
for j in ind:
l1=ind[j][0]
req=(k-j*q)%9
if req==j:
if len(ind[j])>1:
l2=ind[j][1]
ans=min(ans,(l1,l2))
else:
if req in ind and len(ind[req])>0:
l2=ind[req][0]
ans=min(ans,(l1,l2))
if ans==(10**9,10**9):
print(-1,-1)
else:
print(ans[0],ans[1])#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long int n,q,w,i,j;
string s;
cin>>s;
cin>>w;
cin>>q;
n=s.size();
int a[n];
a[n-1]=s[n-1]-'0';
for(i=n-2;i>=0;i--){
a[i]=s[i]-'0'+a[i+1];
}
map< int,vector<pair< int, int> >>m;
for(i=0 ; i <= n-w ; i++)
{
int x;
if(i!=n-w) x=a[i]-a[i+w];
else x=a[i];
m[x%9].push_back(make_pair(i,x));
}
for(i=0 ; i < 9 ; i++)
{
sort(m[i].begin(),m[i].end());
}
while(q--){
int l,r,k;
cin>>l>>r>>k;
l--,r--;
int x=a[l],z,p=1000000000,ans,v;
if(r!=n-1)x=a[l]-a[r+1];
x=x%9;
for(i=0 ; i < 9 ; i++)
{
z=(27+k-(x*i)%9)%9;
if(z!=i && m[z].size()>0 && m[i].size()>0){
v=m[i][0].first;
p=min(p,v);
if(p==v)ans=i;
}
else if(z==i && m[i].size()>1){
v=m[i][0].first;
p=min(v,p);
if(p==v)ans=i;
}
}
if(p==1000000000)cout<<-1<<" "<<-1<<endl;
else{
// cout<<1<<endl;
z=(27+k-(x*ans)%9)%9;
if(z==ans)cout<<m[ans][0].first+1<<" "<<m[ans][1].first+1<<endl;
else cout<<m[ans][0].first+1<<" "<<m[z][0].first+1<<endl;
}
}
}
} 1351. Count Negative Numbers in a Sorted Matrix | 617. Merge Two Binary Trees |
1450. Number of Students Doing Homework at a Given Time | 700. Search in a Binary Search Tree |
590. N-ary Tree Postorder Traversal | 589. N-ary Tree Preorder Traversal |
1299. Replace Elements with Greatest Element on Right Side | 1768. Merge Strings Alternately |
561. Array Partition I | 1374. Generate a String With Characters That Have Odd Counts |
1822. Sign of the Product of an Array | 1464. Maximum Product of Two Elements in an Array |
1323. Maximum 69 Number | 832. Flipping an Image |
1295. Find Numbers with Even Number of Digits | 1704. Determine if String Halves Are Alike |
1732. Find the Highest Altitude | 709. To Lower Case |
1688. Count of Matches in Tournament | 1684. Count the Number of Consistent Strings |
1588. Sum of All Odd Length Subarrays | 1662. Check If Two String Arrays are Equivalent |
1832. Check if the Sentence Is Pangram | 1678. Goal Parser Interpretation |
1389. Create Target Array in the Given Order | 1313. Decompress Run-Length Encoded List |
1281. Subtract the Product and Sum of Digits of an Integer | 1342. Number of Steps to Reduce a Number to Zero |
1528. Shuffle String | 1365. How Many Numbers Are Smaller Than the Current Number |